//70:爬楼梯
//假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
//
// 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
//
//
//
// 示例 1：
//
//
//输入：n = 2
//输出：2
//解释：有两种方法可以爬到楼顶。
//1. 1 阶 + 1 阶
//2. 2 阶
//
// 示例 2：
//
//
//输入：n = 3
//输出：3
//解释：有三种方法可以爬到楼顶。
//1. 1 阶 + 1 阶 + 1 阶
//2. 1 阶 + 2 阶
//3. 2 阶 + 1 阶
//
//
//
//
// 提示：
//
//
// 1 <= n <= 45
// 0 0 1 2
// Related Topics 记忆化搜索 数学 动态规划 👍 2429 👎 0
// 解题思路：本质是二叉树的遍历，也类似于费波纳数列
// 动态规划第一步，先找到转移方程：考虑最后一步可能跨了一级台阶，也可能跨了两级台阶，所以我们可以列出如下式子 f(x) = f(x - 1) + f(x - 2)，
// 第二步，用「滚动数组思想」把空间复杂度优化成 O(1)


public class ClimbStairs {
    public static void main(String[] args) {
        int n = 3;
        System.out.println(climbStairs(n));
    }

    public static int climbStairs(int n) {
        int p2 = 0;//N-2的方案数，初始为0阶梯方案数
        int p1 = 1;//n-1的方案数，初始为1阶梯方案数
        int r = 2;//n的方案数，初始为2阶梯方案数
        if (n == 1) {
            return p1;
        }
        for (int i = 3; i <= n; i++) {
            p2 = p1;
            p1 = r;
            r = p1 + p2;
        }
        return r;
    }
}
